package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DesignProblem;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode.com/problems/all-oone-data-structure/
 *
 * Challenge: Perform all these in O(1) time complexity.
 * <p>
 * https://leetcode.com/problems/all-oone-data-structure/discuss/91416/Java-AC-all-strict-O(1)-not-average-O(1)-easy-to-read
 *
 * @author tzp
 * @since 2020/11/16
 */
public class LC432 implements DesignProblem {

    class AllOne {
        class CountBucket {
            Set<String> keys = new HashSet<>();
            CountBucket pre;
            CountBucket next;
        }

        HashMap<String, Integer> data = new HashMap<>();
        HashMap<Integer, CountBucket> cnt = new HashMap<>();
        CountBucket head = new CountBucket();
        CountBucket tail = new CountBucket();

        public AllOne() {
            head.next = tail;
            tail.pre = head;
        }

        public void inc(String key) {
            int oldCnt = 0, newCnt = 0;
            if (data.containsKey(key)) {
                oldCnt = data.get(key);
                newCnt = data.get(key) + 1;
            } else {
                oldCnt = 0;
                newCnt = 1;
            }
            data.put(key, newCnt);
            //更新cnt
            CountBucket oldBucket = cnt.get(oldCnt);
            cnt.compute(newCnt, (k, mergeV) -> {
                if (mergeV == null) {
                    mergeV = new CountBucket();
                    if (oldBucket == null) {
                        CountBucket tmp = head.next;
                        head.next = mergeV;
                        mergeV.pre = head;
                        mergeV.next = tmp;
                        tmp.pre = mergeV;
                    } else {
                        CountBucket tmp = oldBucket.next;
                        oldBucket.next = mergeV;
                        mergeV.pre = oldBucket;
                        mergeV.next = tmp;
                        tmp.pre = mergeV;
                    }
                }
                mergeV.keys.add(key);
                return mergeV;
            });
            if (oldBucket != null) {
                cnt.get(oldCnt).keys.remove(key);
                if (cnt.get(oldCnt).keys.size() == 0) {
                    oldBucket.pre.next = oldBucket.next;
                    oldBucket.next.pre = oldBucket.pre;
                    cnt.remove(oldCnt);
                }
            }
        }

        public void dec(String key) {
            if (data.containsKey(key)) {
                int oldCnt = data.get(key);
                int newCnt = data.get(key) - 1;
                if (newCnt == 0) {
                    data.remove(key);
                } else {
                    data.put(key, newCnt);
                }
                //更新cnt
                CountBucket oldBucket = cnt.get(oldCnt);
                if (newCnt != 0) {
                    cnt.compute(newCnt, (k, mergeV) -> {
                        if (mergeV == null) {
                            mergeV = new CountBucket();
                            mergeV.pre = oldBucket.pre;
                            oldBucket.pre.next = mergeV;
                            mergeV.next = oldBucket;
                            oldBucket.pre = mergeV;
                        }
                        mergeV.keys.add(key);
                        return mergeV;
                    });
                }
                if (oldBucket != null) {
                    cnt.get(oldCnt).keys.remove(key);
                    if (cnt.get(oldCnt).keys.size() == 0) {
                        oldBucket.pre.next = oldBucket.next;
                        oldBucket.next.pre = oldBucket.pre;
                        cnt.remove(oldCnt);
                    }
                }
            }
        }

        public String getMaxKey() {
            return data.size() > 0 ? tail.pre.keys.iterator().next() : "";
        }

        public String getMinKey() {
            return data.size() > 0 ? head.next.keys.iterator().next() : "";
        }
    }


    //"inc","inc","inc","inc","inc","inc","getMaxKey","getMinKey"]
    //["new"],["new"],["new"],["new"],["new"],["new"],[],[]]
    public static void main(String[] args) {
        AllOne allOne = new LC432().new AllOne();
        allOne.inc("hello");
        allOne.inc("world");
        allOne.inc("leet");
        allOne.inc("code");
        allOne.inc("DS");
        allOne.inc("leet");
        System.out.println(allOne.getMaxKey());
        allOne.inc("DS");
        allOne.dec("leet");
        System.out.println(allOne.getMaxKey());
        allOne.dec("DS");
        allOne.inc("hello");
        System.out.println(allOne.getMaxKey());
        allOne.inc("hello");
        allOne.inc("hello");
        allOne.dec("world");
        allOne.dec("leet");
        allOne.dec("code");
        allOne.dec("DS");
        System.out.println(allOne.getMaxKey());
        allOne.inc("new");
        allOne.inc("new");
        allOne.inc("new");
        allOne.inc("new");
        allOne.inc("new");
        allOne.inc("new");
        System.out.println(allOne.getMaxKey());
        System.out.println(allOne.getMinKey());
    }
}
